/**
 * 
 */
package No1_100.No11_20.GenerateParentheses_22;

import java.util.ArrayList;
import java.util.List;

/** 
 * @author  作者 E-mail: ttljtw@qq.com
 * @date 创建时间：2017年3月4日 下午7:41:58 
 * @version 1.0 
 * @parameter  
 * @since  
 * @return  
 */
/**
 * @author 李敬
 *
 */
public class Solution {
	
	/*
	 * 描述：给定一个非负整数n，生成n对括号的所有合法排列。
	 * 如n=3,
	 * [
	 *   "((()))",
	 *   "(()())",
	 *   "(())()",
	 *   "()(())",
	 *   "()()()"
	 * ]
	 * */
	
    public List<String> generateParenthesis(int n) {//基本完成，String s 的技巧需要掌握
        List<String> ret = new ArrayList<>();
        function(n,0,0,"",ret);
        return ret;
    }
    void function(int n,int countA,int countB,String s,List<String> ret){
        if(countA >= n && countB >= n){
            ret.add(s);
            return ;
        }else{
            if(countA < n){
                function(n,countA+1,countB,s+'(',ret);
            }
            if(countB < countA){
                function(n,countA,countB+1,s+')',ret);
            }
        }
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
